<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>二叉树任务调度 LCP10</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="二叉树任务调度-lcp10">二叉树任务调度 LCP10</h1>
<ul>
<li><a href="https://leetcode-cn.com/problems/er-cha-shu-ren-wu-diao-du/">https://leetcode-cn.com/problems/er-cha-shu-ren-wu-diao-du/</a></li>
<li><a href="https://zhuanlan.zhihu.com/p/146655753">https://zhuanlan.zhihu.com/p/146655753</a></li>
</ul>
<p>本地代码不长，但是很抽象。 关键是求出每个子树的最大并行时间, 要么为(a+c)/2, 要么为 b+c.  最后的答案就是 总任务时间 - 最大并行时间</p>
<h2 id="题目描述">题目描述</h2>
<p>任务调度优化是计算机性能优化的关键任务之一。在任务众多时，不同的调度策略可能会得到不同的总体执行时间，因此寻求一个最优的调度方案是非常有必要的。</p>
<p>通常任务之间是存在依赖关系的，即对于某个任务，你需要先完成他的前导任务（如果非空），才能开始执行该任务。我们保证任务的依赖关系是一棵二叉树，其中 root 为根任务，root.left 和 root.right 为他的两个前导任务（可能为空），root.val 为其自身的执行时间。</p>
<p>在一个 CPU 核执行某个任务时，我们可以在任何时刻暂停当前任务的执行，并保留当前执行进度。在下次继续执行该任务时，会从之前停留的进度开始继续执行。暂停的时间可以不是整数。</p>
<p>现在，系统有两个 CPU 核，即我们可以同时执行两个任务，但是同一个任务不能同时在两个核上执行。给定这颗任务树，请求出所有任务执行完毕的最小时间。</p>
<h2 id="解法一">解法一</h2>
<p>设一颗任务树的左子树所有任务时间和为 a ，最大并行时间为 b ，右子树分别为 c ， d 。那么这颗任务树最大并行时间为 (a+c)/2 ，但不一定能取到。</p>
<p>不失一般性，假设 a&gt;=c 。如果 a-2*b &lt;= c ，那么最优策略是左树先并行 a-c 的任务，这样左右两个子树都剩余 c 的任务量，然后再两树并行，就达成了一直并行。并行时间取到了 (a+c)/2 。</p>
<p>如果 a-2*b&gt;c ，那么剩余 a-2b-c 的任务无法被并行。并行时间最大为 (b+c) 。</p>
<pre><code class="language-python"><div><span class="hljs-comment"># Definition for a binary tree node.</span>
<span class="hljs-comment"># class ceeNode(object):</span>
<span class="hljs-comment">#     def __init__(self, x):</span>
<span class="hljs-comment">#         self.val = x</span>
<span class="hljs-comment">#         self.left = None</span>
<span class="hljs-comment">#         self.right = None</span>

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minimalExecTime</span><span class="hljs-params">(self, root)</span>:</span>
        <span class="hljs-string">"""
        :type root: TreeNode
        :rtype: float
        """</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(root)</span>:</span>
            <span class="hljs-keyword">if</span> root <span class="hljs-keyword">is</span> <span class="hljs-literal">None</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-number">0.</span>, <span class="hljs-number">0.</span>
            tc = root.val
      
            <span class="hljs-comment"># 先递归左右子树</span>
            a, b = dfs(root.left)
            c, d = dfs(root.right)
            
            tc = tc + a + c
            <span class="hljs-comment"># 只考虑 a &gt;= c 的情况，不满足就交换</span>
            <span class="hljs-keyword">if</span> a &lt; c:
                a, c = c, a
                b, d = d, b
            
            <span class="hljs-keyword">if</span> a - <span class="hljs-number">2</span> * b &lt;= c:
                pc = (a + c) / <span class="hljs-number">2</span>
            <span class="hljs-keyword">else</span>:
                pc = c + b

            <span class="hljs-keyword">return</span> tc, pc

        tc, pc = dfs(root)
        <span class="hljs-keyword">return</span> tc - pc
</div></code></pre>

    </body>
    </html>